class Solution
{
public:
    int divide(int dividend, int divisor)
    {
        if (divisor == INT_MIN)
        {
            return dividend == INT_MIN ? 1 : 0;
        }

        bool intMinCast = false;
        bool isPositive = true;
        if (dividend == INT_MIN)
        {
            if (divisor == -1)
            {
                return INT_MAX;
            }
            if (divisor == 1)
            {
                return INT_MIN;
            }
            intMinCast = true;
            isPositive = false;
            dividend = INT_MAX;
        }

        if (dividend < 0)
        {
            dividend = -dividend;
            isPositive = !isPositive;
        }

        if (divisor < 0)
        {
            divisor = -divisor;
            isPositive = !isPositive;
        }

        int result = 0;
        int num = dividend;
        int power = 1;
        int powerDivisor = divisor;
        constexpr int HALF_INT_MAX = INT_MAX >> 1;
        while (true)
        {
            if (num >= powerDivisor)
            {
                result += power;
                num -= powerDivisor;
                if (powerDivisor < HALF_INT_MAX)
                {
                    powerDivisor += powerDivisor;
                    power = power << 1;
                }
            }
            else if (power > 1)
            {
                power = 1;
                powerDivisor = divisor;
            }
            else
            {
                break;
            }
        }

        if (intMinCast && num + 1 == divisor)
        {
            ++result;
        }

        if (!isPositive)
        {
            result = -result;
        }
        return result;
    }
};